const RedBlackTree = require("../template")

function testRedBlackTreeComplexScenarios() {
  console.log(
    "1. 复杂插入序列测试:",
    (() => {
      const rbt = new RedBlackTree()
      
      // 复杂的插入序列，测试各种旋转情况
      const complexSequence = [
        50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45, 55, 65, 75, 85,
        5, 15, 22, 27, 32, 37, 42, 47, 52, 57, 62, 67, 72, 77, 82, 87
      ]
      
      complexSequence.forEach(val => rbt.insert(val))
      
      // 验证所有值都存在
      const allFound = complexSequence.every(val => rbt.search(val) !== null)
      
      return allFound &&
             rbt.getSize() === complexSequence.length &&
             rbt.isValid() === true
    })()
  )

  console.log(
    "2. 复杂删除序列测试:",
    (() => {
      const rbt = new RedBlackTree()
      
      // 插入数据
      const values = [50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45, 55, 65, 75, 85]
      values.forEach(val => rbt.insert(val))
      
      // 复杂的删除序列
      const deleteSequence = [50, 30, 70, 20, 40] // 删除根节点和内部节点
      deleteSequence.forEach(val => rbt.delete(val))
      
      // 验证删除结果
      const deletedCorrect = deleteSequence.every(val => rbt.search(val) === null)
      const remainingCorrect = values.filter(val => !deleteSequence.includes(val))
        .every(val => rbt.search(val) !== null)
      
      return deletedCorrect &&
             remainingCorrect &&
             rbt.getSize() === values.length - deleteSequence.length &&
             rbt.isValid() === true
    })()
  )

  console.log(
    "3. 重复插入删除测试:",
    (() => {
      const rbt = new RedBlackTree()
      
      // 重复插入和删除
      for (let round = 0; round < 5; round++) {
        // 插入数据
        for (let i = 1; i <= 10; i++) {
          rbt.insert(i)
        }
        
        // 删除部分数据
        for (let i = 1; i <= 5; i++) {
          rbt.delete(i)
        }
        
        // 重新插入
        for (let i = 1; i <= 5; i++) {
          rbt.insert(i)
        }
      }
      
      // 验证最终状态
      let allFound = true
      for (let i = 1; i <= 10; i++) {
        if (rbt.search(i) === null) {
          allFound = false
          break
        }
      }
      
      return allFound &&
             rbt.getSize() === 10 &&
             rbt.isValid() === true
    })()
  )

  console.log(
    "4. 边界值处理测试:",
    (() => {
      const rbt = new RedBlackTree()
      
      // 测试边界值
      const boundaryValues = [
        Number.MAX_SAFE_INTEGER,
        Number.MIN_SAFE_INTEGER,
        0,
        -1,
        1,
        Math.pow(2, 31) - 1,
        -Math.pow(2, 31)
      ]
      
      boundaryValues.forEach(val => rbt.insert(val))
      
      // 验证所有边界值都存在
      const allFound = boundaryValues.every(val => rbt.search(val) !== null)
      
      // 验证最小值和最大值
      const min = rbt.getMin()
      const max = rbt.getMax()
      const expectedMin = Number.MIN_SAFE_INTEGER
      const expectedMax = Number.MAX_SAFE_INTEGER
      
      return allFound &&
             min === expectedMin &&
             max === expectedMax &&
             rbt.getSize() === boundaryValues.length &&
             rbt.isValid() === true
    })()
  )

  console.log(
    "5. 大量数据管理测试:",
    (() => {
      const rbt = new RedBlackTree()
      const count = 5000
      
      // 插入大量数据
      for (let i = 0; i < count; i++) {
        rbt.insert(i)
      }
      
      // 随机访问测试
      const randomIndices = Array.from({ length: 100 }, () => 
        Math.floor(Math.random() * count)
      )
      
      const randomAccessCorrect = randomIndices.every(index => 
        rbt.search(index) !== null
      )
      
      // 验证统计信息
      const height = rbt.getHeight()
      const size = rbt.getSize()
      const maxHeight = 2 * Math.log2(count + 1)
      
      return randomAccessCorrect &&
             size === count &&
             height <= maxHeight &&
             rbt.isValid() === true
    })()
  )

  console.log(
    "6. 动态负载测试:",
    (() => {
      const rbt = new RedBlackTree()
      
      // 阶段1：插入数据
      for (let i = 0; i < 1000; i++) {
        rbt.insert(i)
      }
      
      const height1 = rbt.getHeight()
      const size1 = rbt.getSize()
      
      // 阶段2：删除部分数据
      for (let i = 0; i < 500; i++) {
        rbt.delete(i)
      }
      
      const height2 = rbt.getHeight()
      const size2 = rbt.getSize()
      
      // 阶段3：重新插入
      for (let i = 0; i < 500; i++) {
        rbt.insert(i)
      }
      
      const height3 = rbt.getHeight()
      const size3 = rbt.getSize()
      
      return height1 <= 2 * Math.log2(size1 + 1) &&
             height2 <= 2 * Math.log2(size2 + 1) &&
             height3 <= 2 * Math.log2(size3 + 1) &&
             size1 === 1000 &&
             size2 === 500 &&
             size3 === 1000 &&
             rbt.isValid() === true
    })()
  )

  console.log(
    "7. 并发操作模拟测试:",
    (() => {
      const rbt = new RedBlackTree()
      
      // 模拟多个操作同时进行
      const operations = []
      
      // 操作1：批量插入
      for (let i = 0; i < 100; i++) {
        operations.push(() => rbt.insert(i))
      }
      
      // 操作2：批量搜索
      for (let i = 0; i < 100; i++) {
        operations.push(() => rbt.search(i))
      }
      
      // 操作3：批量删除
      for (let i = 0; i < 50; i++) {
        operations.push(() => rbt.delete(i))
      }
      
      // 随机执行操作
      const shuffledOps = operations.sort(() => Math.random() - 0.5)
      shuffledOps.forEach(op => op())
      
      // 验证最终状态
      const finalSize = rbt.getSize()
      const isValid = rbt.isValid()
      
      return finalSize === 50 && // 100 - 50 = 50
             isValid === true
    })()
  )

  console.log(
    "8. 错误恢复测试:",
    (() => {
      const rbt = new RedBlackTree()
      
      // 正常操作
      rbt.insert(50)
      rbt.insert(30)
      rbt.insert(70)
      
      // 尝试一些边界操作
      rbt.insert(50) // 重复插入
      rbt.delete(100) // 删除不存在的值
      rbt.delete(30) // 正常删除
      
      // 验证状态
      const size = rbt.getSize()
      const isValid = rbt.isValid()
      
      return size === 2 && // 50, 70
             isValid === true &&
             rbt.search(50) !== null &&
             rbt.search(70) !== null &&
             rbt.search(30) === null &&
             rbt.search(100) === null
    })()
  )

  console.log(
    "9. 内存效率测试:",
    (() => {
      const rbt = new RedBlackTree()
      
      // 添加大量数据测试内存效率
      const startMemory = process.memoryUsage ? process.memoryUsage().heapUsed : 0
      
      for (let i = 0; i < 2000; i++) {
        rbt.insert(i)
      }
      
      const endMemory = process.memoryUsage ? process.memoryUsage().heapUsed : 0
      const memoryUsed = endMemory - startMemory
      
      // 验证统计信息
      const height = rbt.getHeight()
      const size = rbt.getSize()
      const maxHeight = 2 * Math.log2(size + 1)
      
      return rbt.getSize() === 2000 &&
             height <= maxHeight &&
             rbt.isValid() === true &&
             memoryUsed < 50 * 1024 * 1024 // 内存使用应该合理
    })()
  )

  console.log(
    "10. this上下文复杂场景测试:",
    (() => {
      const complexObj = {
        multiplier: 3,
        processComplex: function(values) {
          const rbt = new RedBlackTree()
          values.forEach(val => rbt.insert(val))
          return rbt.getSize() * this.multiplier
        }
      }
      
      const testValues = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
      const result = complexObj.processComplex(testValues)
      
      return result === 30 // 10 * 3 = 30
    })()
  )

  console.log(
    "11. 复杂对象this绑定场景测试:",
    (() => {
      const complexConfigObj = {
        config: { 
          threshold: 5, 
          maxHeight: 10 
        },
        processWithComplexConfig: function(values) {
          const rbt = new RedBlackTree()
          values.forEach(val => rbt.insert(val))
          return rbt.getSize() >= this.config.threshold &&
                 rbt.getHeight() <= this.config.maxHeight
        }
      }
      
      const testValues = [10, 20, 30, 40, 50, 60, 70, 80]
      return complexConfigObj.processWithComplexConfig(testValues) === true
    })()
  )

  console.log(
    "12. 综合复杂场景测试:",
    (() => {
      const rbt = new RedBlackTree()
      
      // 综合测试：多种操作混合
      const operations = []
      
      // 插入各种数据
      for (let i = 0; i < 100; i++) {
        operations.push(() => rbt.insert(i))
        operations.push(() => rbt.insert(i + 1000)) // 大数值
        operations.push(() => rbt.insert(-i)) // 负数值
      }
      
      // 执行操作
      operations.forEach(op => op())
      
      // 删除部分数据
      for (let i = 0; i < 50; i++) {
        rbt.delete(i)
        rbt.delete(i + 1000)
      }
      
      // 验证最终状态
      const finalStats = {
        size: rbt.getSize(),
        height: rbt.getHeight(),
        isValid: rbt.isValid(),
        min: rbt.getMin(),
        max: rbt.getMax()
      }
      
      // 验证所有统计信息都合理
      return finalStats.size === 250 && // 300 - 50 = 250
             finalStats.height <= 2 * Math.log2(finalStats.size + 1) &&
             finalStats.isValid === true &&
             finalStats.min === -99 && // 最小的负值
             finalStats.max === 1099 && // 最大的正值
             typeof finalStats.size === 'number' &&
             typeof finalStats.height === 'number' &&
             typeof finalStats.isValid === 'boolean' &&
             typeof finalStats.min === 'number' &&
             typeof finalStats.max === 'number'
    })()
  )
}

testRedBlackTreeComplexScenarios()
